import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author: shiding
 * @data: 2022/5/28 15:21
 **/
public class DetectCycle {


    public static void main(String[] args) {

    }

    /**
     * 暴利解法：
     * 1、初始化 set
     * 2、遍历列表 将每个节点 存储到 set中
     * 3、当出现第一个 set 中存在的元素时，则这个节点就是 环形链表 入环的节点
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {
        ListNode p = head;
        Set<ListNode> nodes = new HashSet();
        while (p != null) {
            if (nodes.contains(p)) {
                return p;
            } else {
                nodes.add(p);
            }
            p = p.next;
        }
        return null;
    }

    /**
     * 使用 快慢指针
     * 1、slow 走1步 fast 走2步  及 当slow走到一半的时候，fast 已经追上了他
     * 2、如果是环形链表的话 追上后 将 fasi 从新初始化为 head 节点 ，并 slow 和 fast 遍历 每次都走1步
     *
     * @param head
     * @return
     */
    public ListNode detectCycle2(ListNode head) {
        ListNode slow = head, fast = head;
        while (true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
}
